import java.util.*;
import java.lang.Math.*;

public class heap {
	
/*	public heap (int s) {
		a = new int[s];
	}*/
	
//	private int a[];
	private int heapSize;
	
	public int getParent (int i) {
		return (int) Math.floor (i / 2);
	}
	
	public int getLeft (int i) {
		return ((2 * i) + 1);
	}
	
	public int getRight (int i) {
		return ((2 * i + 1) + 1);
	}
	
	public void maxHeapify (int a[], int i) {
		int l = getLeft (i);
		int r = getRight (i);
//		System.out.println("i="+i+" l="+l+" r="+r);
		int largest;
		if ( (l < heapSize) && (a[l] > a[i]) ) {
			largest = l;
		} else {
			largest = i;
		}
		if ( (r < heapSize) && (a[r] > a[largest]) ) {
			largest = r;
		}
		if (largest != i) {
			int tmp = a[i];
			a[i] = a[largest];
			a[largest] = tmp;
			maxHeapify (a, largest);
		}
	}
	
	public void buildMaxHeap (int a[]) {
//		a = new int[ap.length];
		heapSize = a.length;
		for (int i = (int) Math.floor (a.length / 2) - 1; i >= 0; i-- ) {
			maxHeapify (a, i);
		}
	}
	
	public void heapsort (int a[]) {
		buildMaxHeap (a);
		
		for (int i = (a.length - 1); i > 0; i--) {
			int tmp = a[0];
			a[0] = a[i];
			a[i] = tmp;
			heapSize--;
			maxHeapify (a, 0);
		}
	}
	
	public static void main (String[] args) {
		heap h = new heap ();
		int a[] = new int[]{16,4,10,14,7,9,3,2,8,1};
		//h.heapsort (a);
		System.out.println (Arrays.toString (a));
		//h.maxHeapify(a, 1);
		h.buildMaxHeap (a);
		System.out.println (Arrays.toString (a));
		h.heapsort (a);
		System.out.println (Arrays.toString (a));
	}	
	
}
